package Hard;
// 答案看不懂 放弃。
import com.sun.source.tree.Tree;

import java.util.*;

// 850.矩形面积II
/*
 * 暴力解法，定义一个1000000000*1000000000大小的矩阵，每个点代表这个地方有没有面积
 * 超出内存限制 --> 暴力解法完全行不通！
 * 答案思路1： 暴力扫描 因为矩形最多200个
 *   先取所有矩形(x,y,a,b)的下标x和a,加入到treeSet中，同时lengthmap<Integer,TreeSet>将x~a作为key，分别存入value：y和b
 *   对treeSet从小到大排序后，treeSet中存放的就是把所有矩形，按照竖线分割后，能分割的区域
 *   lengthmap存放的就是，每条竖线，有哪些y点的集合，求面积的时候，把map里的set排序后，两两相减之和就是这个区间的面积
 * 结果： 超出内存限制 --> 这暴力解法还是明显行不通啊！
 * 优化：lengthmap里不要存x~a，就只存x和a-1，当下一次要存的x如果是在已有的两数之间，那么把它的结果复制过去一份，再存自己的
 * */
public class Solution850 {


    public int rectangleArea(int[][] rectangles) {
        long sum = 0;
        Set<Integer> treeSet = new TreeSet<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2; // 如果o1比o2小，那么o1排在o2前面
            }
        });
        Map<Integer, TreeSet<Integer>> hashMap = new HashMap<Integer, TreeSet<Integer>>();
        for (int i = 0; i < rectangles.length; i++) {
            int x = rectangles[i][0];
            int y = rectangles[i][1];
            int a = rectangles[i][2];
            int b = rectangles[i][3];
            // 现存map再存set
            for (int j = x; j < a; j = a - 1) { // 只存x和a-1
                if (hashMap.containsKey(j)) {
                    TreeSet<Integer> set = hashMap.get(j);
                    set.add(y);
                    set.add(b);
                } else {
                    // 寻找j是否已经在hashMap的两数之间
                    Set<Integer> integers = hashMap.keySet();
                    Object[] sets = integers.toArray();

                    int l = -1, r = -1;
                    if (sets.length < 2 || (int) sets[0] > j || (int) sets[sets.length - 1] < j) {
                        TreeSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
                            @Override
                            public int compare(Integer o1, Integer o2) {
                                return o1 - o2;
                            }
                        });
                        set.add(y);
                        set.add(b);
                        hashMap.put(j, set);
                    } else {
                        for (int k = 0; k < sets.length; k++) {
                            if ((int) sets[k] > j) {
                                l = (int) sets[k - 1];
                                break;
                            }
                        }
                        TreeSet<Integer> set = new TreeSet<Integer>(new Comparator<Integer>() {
                            @Override
                            public int compare(Integer o1, Integer o2) {
                                return o1 - o2;
                            }
                        });
                        set.add(y);
                        set.add(b);
                        TreeSet<Integer> lSet = hashMap.get(l);
                        for (Integer h : lSet) {
                            set.add(h);
                        }
                        hashMap.put(j, set);
                    }


                }
                if (j == a - 1)
                    break;
            }
            treeSet.add(x);
            treeSet.add(a);
        }
        // 求面积和
        int preX, x;
        long disctinctX, distinctY;
        TreeSet<Integer> preYset;
        Object[] sets = treeSet.toArray(); // sets存放的是可能的扫描线分割后的矩形区间
        preX = (int) sets[0];
        preYset = hashMap.get(preX);
        for (int i = 1; i < sets.length; i++) {
            x = (int) sets[i];
            disctinctX = x - preX;
            distinctY = 0;
            if (preYset == null) {
                preX = x;
                preYset = hashMap.get(preX);
                continue;
            }
            Object[] ysets = preYset.toArray();
            for (int j = 1; j < ysets.length; j++) {
                distinctY += (int) ysets[j] - (int) ysets[j - 1];
            }
            sum += disctinctX * distinctY;
            sum %= (1_000_000_000 + 7);
            preX = x;
            preYset = hashMap.get(preX);
        }
        return (int) sum;
    }

    public static void main(String[] args) {
        Solution850 s = new Solution850();
        int rec[][] = new int[][]{{0, 0, 2, 2}, {1, 0, 2, 3}, {1, 0, 3, 1}};
        int rec2[][] = new int[][]{{0, 0, 1_000_000_000, 1_000_000_000}};
        int rec3[][] = new int[][]{{0, 0, 1, 1}, {2, 2, 3, 3}};
        int i = s.rectangleArea(rec);
        int j = s.rectangleArea(rec2);
        int k = s.rectangleArea(rec3);
        System.out.println(i);
        System.out.println(j);
        System.out.println(k);
    }
}
